package io.github.hadyang.leetcode.bytedance;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * 合并区间
 *
 * <p>给出一个区间的集合，请合并所有重叠的区间。
 *
 * <p>示例 1:
 *
 * <p>输入: [[1,3],[2,6],[8,10],[15,18]]
 *
 * <p>输出: [[1,6],[8,10],[15,18]]
 *
 * <p>解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 *
 * <p>示例 2:
 *
 * <p>输入: [[1,4],[4,5]]
 *
 * <p>输出: [[1,5]]
 *
 * <p>解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
 */
public class Array1046 {

  @Test
  public void test() {
    Interval interval1 = new Interval(1, 3);
    Interval interval2 = new Interval(2, 6);
    Interval interval3 = new Interval(8, 10);
    Interval interval4 = new Interval(15, 18);

    List<Interval> intervals = new ArrayList<>();
    intervals.add(interval1);
    intervals.add(interval2);
    intervals.add(interval3);
    intervals.add(interval4);

    System.out.println(merge(intervals));
  }

  public class Interval {
    int start;
    int end;

    Interval() {
      start = 0;
      end = 0;
    }

    Interval(int s, int e) {
      start = s;
      end = e;
    }

    @Override
    public String toString() {
      return "Interval{" + "start=" + start + ", end=" + end + '}';
    }
  }

  public List<Interval> merge(List<Interval> intervals) {
    if (intervals.size() <= 1) {
      return intervals;
    }

    intervals.sort(Comparator.comparingInt(o -> o.start));

    List<Interval> res = new ArrayList<>();
    res.add(intervals.get(0));

    for (int i = 1; i < intervals.size(); i++) {
      Interval t = intervals.get(i);
      Interval last = res.get(res.size() - 1);
      if (last.end >= t.start) {
        if (last.end < t.end) last.end = t.end;
      } else {
        res.add(t);
      }
    }

    return res;
  }
}
